#include <vector>
#include <algorithm>
#include <utility>
using std::vector;
using std::pair;
using std::sort;
using std::make_pair;
using std::swap;

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int n=numbers.size();
        vector< pair<int, int> > tmpVector;
        for (int i=0;i<n;i++) tmpVector.push_back(make_pair(numbers[i], i+1));
        sort(tmpVector.begin(), tmpVector.end());
        int h=0, t=tmpVector.size()-1;
        vector<int> ans;
        while (h<t){
            if (tmpVector[h].first+tmpVector[t].first==target){
                ans.push_back(tmpVector[h].second);
                ans.push_back(tmpVector[t].second);
                if (ans[0]>ans[1]) swap(ans[0], ans[1]);
                return ans;
            } else
            if (h<t && tmpVector[h].first+tmpVector[t].first>target) --t; else
            if (h<t && tmpVector[h].first+tmpVector[t].first<target) ++h;
        }
        return ans;
    }
};
